package 排序;
/**
 * @description：插入排序
 * @author: yangyahui01
 * @date: 12/27/24 2:26 PM
 */
public class 插入排序 {
    public static void main(String[] args) {
        int[] nums = {2, 6, 3, 1, 8, 9,1};

        insertSort(nums);

        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    private static void insertSort(int[] nums) {

        for (int i = 1; i < nums.length; i++) {

            int j = i - 1;
            int element = nums[i]; //当前元素

            for (; j >= 0; j--) {
                //找到element应该插入的位置j
                if (element > nums[j]) {
                    break;
                }
                //如果当前元素 < 已排区间的元素,则已排区间的元素往前移动一位
                nums[j+1] = nums[j];

            }
            //将当前元素插入到已排区间合适的位置
            nums[j + 1] = element;
        }

    }
}
